package leetcode;

import java.util.Queue;
import java.util.concurrent.LinkedBlockingQueue;

/**
 * Created with IntelliJ IDEA.
 * User: Ghost
 * Date: 14-6-17
 * Time: 下午2:33
 * To change this template use File | Settings | File Templates.
 */
public class Convert_Sorted_Array_to_Binary_Search_Tree {
    public void sortedToLeft(int[] num,int begin,int end,TreeNode root){
        int mid = (begin+end)/2;
        if(begin<=end){
            root.left = new TreeNode(num[mid]);
            sortedToLeft(num,begin,mid-1,root.left);
            sortedToRight(num,mid+1,end,root.left);
        }
    }
    public void sortedToRight(int[] num,int begin,int end,TreeNode root){
        int mid = (begin+end)/2;
        if(begin<=end){
            root.right = new TreeNode(num[mid]);
            sortedToLeft(num,begin,mid-1,root.right);
            sortedToRight(num,mid+1,end,root.right);
        }
    }
    public TreeNode sortedArrayToBST(int[] num) {
        if(num.length==0)
            return null;
        int size = num.length;
        int mid = size/2;
        TreeNode root = new TreeNode(num[mid]);
        sortedToLeft(num,0,mid-1,root);
        sortedToRight(num,mid+1,size-1,root);
        return root;
    }
    public void Print(TreeNode head){
        if(head!=null){
            Print(head.left);
            System.out.print(head.val+" ");
            Print(head.right);
        }
    }
    public void PrintPre(TreeNode head){
        if(head!=null){
            System.out.print(head.val+" ");
            PrintPre(head.left);
            PrintPre(head.right);
        }
    }
    public static void main(String[] args){
        Convert_Sorted_Array_to_Binary_Search_Tree convert_sorted_array_to_binary_search_tree = new Convert_Sorted_Array_to_Binary_Search_Tree();
        int[] num = {};
        TreeNode head = convert_sorted_array_to_binary_search_tree.sortedArrayToBST(num);
        convert_sorted_array_to_binary_search_tree.Print(head);
        System.out.println();
        convert_sorted_array_to_binary_search_tree.PrintPre(head);
    }
}
